package leetcode.graph.island;

/**
 * 695. 岛屿的最大面积
 *
 */
public class MaxAreaOfIsland {

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rowLen = grid.length;
        int colLen = grid[0].length;
        int maxArea = 0;
        for (int r = 0; r < rowLen; ++r) {
            for (int c = 0; c < colLen; ++c) {
                if (grid[r][c] == 1) {
                    int area = area(grid, r, c);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }


    /**
     * 深度优先遍历 递归实现
     *
     * 方法作用
     *      求当前陆地所在岛屿的面积
     *
     * @param grid  地图
     * @param row   陆地行坐标
     * @param col   陆地列坐标
     * @return      最大面积
     */
    public int area(int[][] grid, int row, int col) {
        int rowLen = grid.length;
        int colLen = grid[0].length;

        if (row < 0 || col < 0 || row >= rowLen || col >= colLen || grid[row][col] == 0) {
            return 0;
        }

        // 已经访问过的陆地设置为0, 防止重复计算岛屿面积
        grid[row][col] = 0;

        // 当前陆地所在岛屿的面积 = 当前陆地面积 + 四周所有陆地的面积
        return 1 + area(grid, row - 1, col) + area(grid, row + 1, col)
                + area(grid, row, col - 1) + area(grid, row, col + 1);
    }


}
